package G.二叉搜索树;

public class _面试题_1712_BiNode {

    public static void main(String[] args) {
        _面试题_1712_BiNode test = new _面试题_1712_BiNode();
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(5);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(6);
        root.left.left.left = new TreeNode(0);
        test.convertBiNode(root);

    }
    /**
     * 自解：递归法 对于节点root来说 左子树的有指针为root root右子数为更新的右子数
     *
     * ---ac不出来
     * @param root
     * @return
     */

    boolean isHead = false;
    TreeNode first = null;
    public TreeNode convertBiNode(TreeNode root) {

        convert(root);
        return first;

    }

    public TreeNode convert(TreeNode root){
        if (root == null) {
            return null;
        }
        if (root.left == null && root.right == null){
            return root;
        }

        TreeNode left = convert(root.left);

        if (left != null){
            if (!isHead){
                //表最左边的叶子节点
                isHead = true;
                first = left;
            }
            left.right = root;
        }else {
            //表示最左边没有叶子
            if (!isHead){
                isHead = true;
                first = root;
            }

        }
        TreeNode right = convert(root.right);
        root.right = right;
        root.left = null;

        return right;
    }


    /**
     *
     * 不需要获取返回值的时候 遍历函数就设置成无返回的即可
     *     中序遍历可以不需要返回值 借助两个指针 prev 用来保留以形成的最后一个 root进入右子数
     */

    TreeNode prev = null;
    TreeNode head = null;
    public TreeNode convertBiNode1(TreeNode root) {

        helper(root);
        return head;

    }

    public void helper(TreeNode root){
        if (root == null){
            return;
        }

        helper(root.left);

        if (prev == null){//表示第一个节点
            head = root;
            prev = root;
        }else {
            prev.right =root;
            prev = root;
        }
        root.left = null;//比不可少

        helper(root.right);
    }

}
